package com.faiz.algorithm;

public class Palindrome {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        // 使用快慢指针找到中间和尾部
        ListNode tmp = new ListNode();
        tmp.next = head;
        ListNode s = tmp, f = tmp;
        int len = 0;
        while (f.next != null) {
            f = f.next;
            len++;
            if (f.next == null) {
                break;
            }
            f = f.next;
            len++;
            s = s.next;
        }
        // 第二部分的开头
        ListNode second = len % 2 == 0 ? s.next : s.next.next;
        ListNode first = reverseList(head, s);
        while (first != null) {
            if (first.val != second.val) return false;
            first = first.next;
            second = second.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head, ListNode end) {
        if (head == end) {
            end.next = null;
            return end;
        }
        ListNode newHead = reverseList(head.next, end);
        head.next.next  = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        Palindrome palindrome = new Palindrome();
        ListNode head = new ListNode(0);
        ListNodeBuilder builder = new ListNodeBuilder(head);
        builder.add(0).add(2).add(2).add(1).add(2).add(2).add(0).add(1);
        System.out.println(palindrome.isPalindrome(head));
    }
}
